package com.tgy.algorithm.base;

/**
 * 1)输入链表头节点，奇数长度返回中点，偶数长度返回上中点
 * 2)输入链表头节点，奇数长度返回中点，偶数长度返回下中点
 * 3)输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
 * 4)输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个
 */
public class _链表快慢指针_02 {


    public static Node generateLink(int[] nums) {

        if (nums == null || nums.length == 0) {
            return null;
        }

        Node header  = new Node(nums[0],null);
        Node cur = header;

        for (int i = 1; i < nums.length; i++) {
            Node node  = new Node(nums[i],  null);
            cur.next = node;
            cur = node;
        }

        return header;
    }

    public static void printLink(Node head) {
        while (head != null) {
            System.out.print(head.num + ",");
            head = head.next;
        }
        System.out.println();
    }

    // 1)输入链表头节点，奇数长度返回中点，偶数长度返回上中点
    public static Node nodeBefore(Node head) {

        if (head == null || head.next == null) {
            return head;
        }

        Node slow = head;
        // 这里写next，则slow在偶数个节点的时候少走一步，则停在两个中心偶数的前一个
        Node fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    //  2)输入链表头节点，奇数长度返回中点，偶数长度返回下中点
    public static Node nodeAfter(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node slow = head;
        Node fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    //  3)输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
    public static Node nodeBeforeBefore(Node head) {

        if (head == null || head.next == null) {
            return null;
        }

        Node slow = head;
        Node fast = head.next.next;

        while (fast != null && fast.next != null  && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    // 4)输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个
    public static Node nodeBeforeAfter(Node head) {
        if (head == null || head.next == null) {
            return null;
        }

        Node slow = head;
        Node fast = head.next.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    public static void main(String[] args) {
        int[] nums = {3,1,2,4,5,6,7};
        Node head = generateLink(nums);
        printLink(head);
//        Node node = nodeBefore(head);
//        Node node = nodeAfter(head);
        Node node = nodeBeforeAfter(head);
        System.out.println(node.num);
    }
}
